#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
struct ListNode{
	int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
		vector<ListNode*> v;
		while(head){
			v.push_back(head);
			head= head->next;
		}
		return v[v.size()/2];
    }
};

int main(){
	ListNode * head = (ListNode *)malloc(sizeof(ListNode));
	head->val= 0;
	head->next = NULL;
	ListNode * start = head;
	for(int i = 1; i < 6; i++){
		ListNode * tmp = (ListNode *)malloc(sizeof(ListNode));
		tmp->val = i;
		tmp->next = NULL;
		head->next = tmp;
		head = tmp;
	}

	Solution so;
	ListNode * mid = so.middleNode(start);
	
	cout << "mid:" << mid->val << endl;
	
	cout << endl;
	return 0;
}